\documentclass[a4paper]{article}
\usepackage[french]{babel}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}

%%\usepackage{algorithm}
%%\usepackage{algorithmic}

%%%%%%%%%% marges %%%%%%%%%%

%%\usepackage{layout}
\usepackage[top=3cm, bottom=3cm, left=4cm, right=4cm]{geometry}



\begin{document}
\title{Simulation d'un Sytème à n corps}

\author{Guillaume \bsc{Boutin}, Cyrille \bsc{Piacibello}}

\maketitle

\section*{Introduction}
L'objectif de ce projet est de simuler sur une architecture parallèle
les interactions gravitationnelles entre différents corps. Chaque
masse est soumise à l'influence de chacune des autres masses. Des
communications sont indispensables car chaque processus n'a pas assez
de mémoire pour stocker touts les masses. 

Dans un premier temps, nous verrons le principe de base, puis nous
expliquerons les détails et améliorations apportées au programme.

\section{Principe de l'algorithme}
Le principe de l'algorithme est d'itérer par approximations
successives les positions des différents corps de chaque processus.
Le programme prend donc en entrée une durée maximum de simulation
(exprimé plus loin en nombre de tours), et un intervalle de temps dt.

\subsection{Déroulement de l'algorithme}
La partie calcul est classique : elle consiste à calculer à chaque étape t les positions des corps à l'étape t+dt
en utilisant leur position, leur vitesse et l'accélération due aux autres masses au temps t. 

\subsection{Communication entre processus}
A chaque itération (calcul de t+dt), chaque processus a besoin de
connaître successivement les positions et masses des corps de chacun
des autre processus. Pour cela, il envoie les informations sur ses
propres masses au processus n+1 et reçoit celles u processus n-1; puis
envoie les données précédemment reçues au processus n+1 à nouveau,
tout en receveant du n-1. Après autant d'échanges qu'il y a de
processus, chacun d'entre eux a eu accès au masses de tout le
monde. Pour limiter l'utilisation mémoire, on ne stocke pas toutes les
données : on utilise deux buffers (un buffer d'envoi et un buffer de
réception) qui alterneront leur rôle à chaque itération. Ainsi,
lorsque le processus reçoit des données dans le buffer 0, il peut
calculer en même temps les accélérations partielles sur ses corps,
dues aux corps présents dans le buffer 1, tout en envoyant les données
du buffer 1 au processus n+1. Il y a donc un buffer en écriture et un
en lecture (calcul et envoi). Puis au prochain tour, il calcule les
accélérations pour les masses nouvellement reçues dans le buffer 0 et
le buffer 1 sert pour la réception.  Les données reçues viennent donc
écraser les données reçues deux tours plus tôt.
\subsection{Calcul des nouvelles positions}
Lorsque chaque processus a calculé l'influence des corps de tous les
autres processus sur les siens, il peut calculer les nouvelles
positions de ses corps et recommencer à communiquer ces valeurs aux
autres.


\section{Améliorations}
 
Nous avons amélioré cette première version à travers deux
modifications : un dt variable et des communications persistantes.

\subsection{Utilisation d'un dt variable}

Lorsque deux corps se trouvent très près l'un de l'autre,
l'interaction qui en résulte est très grande, car c'est une
interaction de type gravitationnelle, donc proportionnelle à l'inverse
du carré de la distance séparant les deux corps.  On obtient donc une
accélération foudroyante car le dt est relativement très grand. Il est
donc intéressant de pouvoir adapter le dt utilisé (par tout le monde)
à chaque itération. 

Pour cela on s'est fixé comme condition que la dista,ce séparant deux
positions successives d'un même corps soit inférieure à 10\% de la
distance le séparant de son voisin le plus proche. Cela revient à
résoudre une équation du second degré en dt. A chaque communication,
nous stockons donc également pour chaque corps, son corps le plus
proche(initialisé au premier trouvé et remplacé par tout corps
rencontré plus proche encore).  Puis après toutes les communications,
on connaît pour chaque corps son corps le plus proche, ce qui nous
permet de calculer le dt optimal du processus.  On utilise alors la
fonction MPI\_Allreduce pour connaître le plus petit dt trouvé sur
chacun des processus et le définir pour chacun comme étant celui à
utiliser pour cette itération. 

NB:Le polynôme obtenu a en général deux racines. Nous choisissons la
plus grande pour garder le dt le plus grand de l'intervalle
satisfaisant l'équation, et donc ne pas réduire inutilement dt.

A noter aussi que nous ne tenons pas compte du dt calculé pour un
corps si la résultante des accélérations sur ce corps est nulle, sinon
cela revient à diviser par 0 lors du calcul de dt. Dans ce cas, le dt
local choisi est celui rentré par l'utilisateur.
\subsection{Utilisation de communications persistantes et non bloquantes}
Les communications d'en un tel cas sont généralement ce qui ralenti
l'exécution. Pour diminuer le temps de communications, nous utilisons
deux mécanismes distincts.

\subsubsection{Communications persistantes}
La bibliotheque MPI permet l'usage de communications persistantes dans
le cas où on repete successivement des communications impliquant les
mêmes processus. C'est ici le cas lors de l'envoie et la reception des
masses des autres processus. Au début de la boucle nous créons deux
requêtes d'envoi, une pour les envois impliquant le buffer 0, l'autre
pour les envois du buffer 0.  Ensuite, à chaque étape de
communication, nous utilisons la fonction \verb!MPI_Start!. Ainsi nous
factorisons le temps d'établissement de communication.

\subsubsection{Communications non bloquantes}
Les envois de données sont bufferisés, c'est à dire qu'on peut
commencer le calcul avant que l'envoi ne soit terminé. De même, on
utilise une reception non bloquante pour qu'aucun processus n'attende
sans calculer. À la fin de chaque étape de communication, on appele la
fonction \verb!MPI_Wait! pour synchroniser les processus.
L'ensembles des communications est réinitialisé à chaque itération.

\section{Résultats obtenus}
Nous avons testé le programme avec des petites valeurs de processus et
de corps par processus en obtenant des résultats satisfaisants.

Pour 3 processus avec un corps chacun et de même masse situés en ligne
(même y et x valant 0, 50 et 100) et avec une même vitesse initiale en
y, nous observons bien que chacun des corps se déplace sur l'axe des y
à la même vitesse, que les corps extrémaux se rapprochent de celui du
milieu, et en fin que celui du milieu ne se déplace pas sur l'axe des
x, car la somme des forces appliquées sur lui est nulle. Le pas de
temps dt diminue également à mesure que les corps se rapprochent les
uns des autres.

Le programme fonctionne encore correctement pour 9 corps répartis sur
3 processus, mais la cohérence des résultats obtenus devient vite
compliquée à vérifier.

Nous avons lancé le programme sur des nombres plus importants (100
corps sur 10 processus), mais nous obtenons des NAN inexpliqués. Nous
n'avons donc pas pu comparer les temps d'exécution de la version avec
et de la version sans communications persistantes avec un nombre de
masses significatifs.

\section*{Conclusion}

Bien que le projet fonctionne, nous n'avons pas pu nous rendre compte
exactement de ce que nous avons obtenu, car la visualisation des
mouvements est difficile. De plus, du fait des limitations de notre
implémentation, nous n'avons pas pu nous rendre compte exactement de
l'apport de communications persistantes et non bloquantes.  

Néanmoins, nous avons pu implémenter de façon fonctionnelle une
approximation d'un problème physique complexe.

\end{document}
